/*问题分析：本质还是一个排序问题
* 解法设想：
* 1、找到x这个值在链表中的位置范围
* 2、遍历链表，将符合条件的节点插入到队首
* 3、关于头节点：a、如果x在表头或表中部，则头节点为第一个插入的节点；b、如果x在表尾，则返回原链表不用动
* 4、关于头节点：a、在原链表前面设置一个空的头节点；b、将第一个遇到的不符合条件的节点设置为新的头节点，所有符合条件的节点将插在该头节点之前*/
import java.util.*;
class ListNode {
    int val;
    ListNode next = null;
    ListNode(){

    }
    ListNode(int val) {
        this.val = val;
    }
}
public class Partition {
    //这是a方法
    public ListNode partition1(ListNode pHead, int x) {
        // write code here
        //设立新的头节点
        ListNode Head = new ListNode();//val为空的新的头节点
        Head.next = pHead;

        /*遍历链表，将符合条件的节点插入到新的头节点之前。注意！插入的第一个节点可能和后续节点的插入方法不一样！*/
        ListNode cur = pHead;
        ListNode newHead = null;//这个节点名称将授予第一个插入Head前的节点
        while (cur != null){
            if (cur.val < x){
//              /*插入到Head之前:插入的第一个节点可能和后续节点的插入方法不一样、而且对于符合条件的节点操作分为
//              取出——插入 两步*/

            }else {
                cur = cur.next;
            }
        }
        /*删除Head节点*/

    }
    //这是b方法
    public ListNode partition2(ListNode pHead, int x) {
        ListNode cur = pHead;
        ListNode Head = null;
        //获得新的头节点，后续所有符合条件的节点都将插入到该节点之前
        while (cur != null){
            if (cur.val < x){
                cur = cur.next;
            }else {
                Head = cur;
                break;
            }
        }//如果遍历完都没找到合适的头节点怎么办？
        //开始插入节点
    }
}